#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>


void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

//堆顶元素向下调整(大堆调整)
void HeapTopAdjust(int* a,int size,int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child+1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void test3()//升序用大堆，降序用小堆
{
	int a[] = { 15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
	int n = sizeof(a) / sizeof(a[0]);
    //从下到上调整为大堆
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		HeapTopAdjust(a, n, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	for (int i = n - 1; i >= 0; i--)
	{
		Swap(&a[i], &a[0]);
		HeapTopAdjust(a, i, 0);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	test3();
	return 0;
}